Shortest path

Alt text

Dijkstra’salgorithm

Dijkstra’s algorithm (pronounced dyke – strah) is a method of finding the shortest path between two points on a graph.
Each point on the graph is called a node or a vertex (for more information on the features and uses of graphs, see Chapter 19).
It is the basis of technology such as GPS tracking and, therefore, is an important part of AI.

Dijkstra’s algorithm simply checks each vertex looking for the shortest path, even if that takes you away from your destination – it pays no attention to direction.
With larger, more complex problems, that can be a time-consuming drawback.
A* algorithm is based on Dijkstra, but adds an extra heuristic (h) value – an ‘intelligent guess’ on how far we have to go to reach the destination most efficiently.